This invention relates to methods of increasing the storage capacity of a Level Five RAID disk array and the expanded array which is produced by such methods.
In the prior art, the term "RAID" disk array has been defined to mean any Redundant Array of Inexpensive Disks; and several different RAID disk arrays have been defined. These include a Level One RAID disk array, a Level Three RAID disk array and a Level Five RAID disk array. See "A Case for Redundant Arrays of Inexpensive Disks (RAID)" by Patterson, et al., Report No. UCB/CSD 87/391, December 1987, Computer Science Division of the University of California at Berkeley.
With a Level Five RAID disk array, both parity and data are striped across a set of several disks. FIG. 1 shows one example of a Level Five RAID disk array in which the array resides on a set of three disks that are labeled Disk 0, Disk 1, and Disk 2. Each disk stores data chunks "D" and parity chunks "P" in one particular column of the array. Each row of the array contains one parity block and two data blocks which are striped across all three of the disks.
In FIG. 1, the first row of the array consists of parity block P(0,1), data chunk D0, and data chunk D1. Also in the FIG. 1 array, the first column consists of parity chunk P(0,1), data chunk D2, data chunk D4, parity chunk P(6,7), and data chunk D8.
Each data chunk and each parity chunk is partitioned on a disk into several physical blocks. A single block is the smallest portion of a chunk that can be separately addressed by a user program with a read or write command. As one simple example, each chunk can consist of two blocks, and each block can consist of 512 bytes plus one cyclic redundant check byte (the "CRC" byte).
In the FIG. 1 array, block 0 in chunk 0 is addressed by a read/write command with a logical address of 0. As this logical address is sequentially incremented by one, the data blocks are addressed the following order: block 1 of chunk D0, block 0 of chunk D1, block 1 of chunk D1, block 2 of chunk D2, block 3 of chunk D2, block 2 of chunk D3, etc. For example, block 6 of chunk D7 has a logical address of 14.
When a block of data is written, the CRC byte within that block is also generated and written. Further, the parity block which has the same block number as the data block is also generated and written. This parity block is written using odd parity or even parity.
With even parity, the exclusive-or of a parity block and all data blocks that have the same block number produces a block of all "0's". For example, when block 0 of chunk D0 is written, block 0 of parity chunk P(0,1) is also written such that it exclusive-or'd with block 0 of chunks D0 and D1 equals a block of all "0's". Conversely, with odd parity, the exclusive-or of a parity block and all data blocks that have the same block number produce a block of all "1's".
During the execution of a read command, the CRC is regenerated from the block of data that is read. If the regenerated CRC differs from the stored CRC, then the block of data which is read contains an error. To correct this error, the erroneous data block is regenerated by a) reading all of the other blocks on the disks which have the same block number as the erroneous data block; and b) exclusive-oring those blocks together.
Consider now the situation where the storage capacity of the FIG. 1 array needs to be increased. One example of how the storage capacity of the FIG. 1 array can be increased in accordance with the prior art is shown in FIG. 2. There, the rows of the FIG. 1 array are expanded by an additional set of two new disks (Disk 3 and Disk 4). As a result, each row in the FIG. 2 array contains a total of five chunks, whereas each row in the FIG. 1 array contains only three chunks. Each chunk in the FIG. 2 array is again partitioned on a disk into several physical blocks, but to simplify the figures these blocks are not shown.
To change the FIG. 1 array to the FIG. 2 array, several steps S1-S6 as shown in FIG. 3 need to be performed. In step S1, the FIG. 1 array is taken "off-line", which means the array cannot be accessed by commands in any user program. Next in steps S2, the content of all data blocks in the FIG. 1 array are read and stored on back-up media, such as magnetic tape.
In step S3, an array configuration map is generated which defines the arrangement of the data blocks and the parity blocks on the disks as shown in FIG. 2. In step S4, the new parity blocks for the FIG. 2 array are generated and stored on the disks 0-4. In step S5, the data blocks are read from the back-up media and written on the disks 0-4. Then in step S6, the FIG. 2 array is put "on-line", which means that the array can now accept commands from a user program.
However, a major drawback with the above-described method of FIG. 3 is that it takes too much time to complete. This is because each of the steps S2, S4 and S5 reads and/or writes huge amounts of data. Step S2, for example, requires a read and a write of every data block on the initial set of disks. Typically, the steps S2-S5 take several hours to complete; and consequently, the FIG. 1 array must be taken off-line while it is expanded.
Accordingly, a primary object of the present invention is to provide a novel method of adding storage capacity to a Level Five RAID disk array in which the above drawback is overcome.